package leetcode_161_180;

public class twoSum_167 {
    public int[] twoSum(int[] numbers, int target) {
        /**
         * 每个输入 只对应唯一的答案 ，不可以 重复使用相同的元素。
         * 必须只使用常量级的额外空间。
         * 这样就肯定不能使用hash表了
         * 先尝试二分查找每个数字,查找范围是后面的所有数字
         * 因为既然可以遍历到此处，前面必然没有对应的数字
         * 2ms
         */
        int len=numbers.length;
        int maxNum=numbers[len-1];
        for(int i=0;i<len;i++){
            int otherNum=target-numbers[i];
            if(otherNum>maxNum)  //需要的数字太大
                continue;
            int index = findNum(numbers, otherNum, i+1, len-1);
            if(index!=-1)
                return new int[]{i+1, index+1};
        }
        return null;
    }
    int findNum(int[] numbers, int target,int start,int end){
        while(start<=end){
            int mid=start+(end-start)/2;
            if(numbers[mid]<target)
                start=mid+1;
            else if(numbers[mid]>target)
                end=mid-1;
            else
                return mid;
        }
        return -1;
    }

    /**
     * 高解
     * 压缩搜索空间
     * 1ms
     */
    public int[] twoSum2(int[] numbers, int target) {
        int i = 0;
        int j = numbers.length - 1;
        //i 和 j 是该数组分别为行和列所形成的矩形的行和列
        //也代表可能满足结果的第一个和第二个数字
        while (i < j) {   //可以搜索的区域
            int sum = numbers[i] + numbers[j];
            if (sum < target) {  //小于目标值，那么整个第i行显然都无法满足条件，因为 j 是此时的最大列
                i++;       //第i行全部舍弃
            } else if (sum > target) {  //小于目标值，那么整个第i行显然都无法满足条件，因为 i 是此时的最小行
                j--;         //第 j 列全部舍弃
            } else {
                return new int[]{i+1, j+1};
            }
        }
        return new int[]{-1, -1};
    }
}
